package org.example.BinaryTree;

public class Convert_binary_search_tree_to_cumulative_tree {
    public static int sum = 0;
    public static void main(String[] args) {
        //把二叉搜索树转换为累加树

        //给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
        //提醒一下，二叉搜索树满足下列约束条件：
        //节点的左子树仅包含键 小于 节点键的节点。
        //节点的右子树仅包含键 大于 节点键的节点。
        //左右子树也必须是二叉搜索树。
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode root = new TreeNode(4);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        search(root);
        sum(root);
        get(root);
        System.out.println();
        search(root);
    }
    public static void get(TreeNode root) {
        if (root==null) return;
        get(root.left);
        int temp = root.val;
        root.val = sum;
        sum-=temp;
        get(root.right);
    }
    public static void sum(TreeNode root){
        if (root==null) return;
        sum(root.left);
        sum+=root.val;
        sum(root.right);
    }
    public static void search(TreeNode root){
        if (root==null) return;
        System.out.print(root.val+" ");
        search(root.left);
        search(root.right);
    }
}
